/* 
 * File:   Graph.cpp
 * Author: chadijir
 * 
 * Created on September 26, 2010, 12:53 PM
 */

#include "Graph.h"
#include <iomanip>
#include <time.h>
#include <stdlib.h>

using namespace std;

/**
 * Inits all static fields and srand
 */
Graph::Graph() {
    minEdgeWeight = 0;
    graphRegularity = 0;
    maxCutWeight = 0;
    maxCutWeightNode = 0;
    nodeCount = 0;
    srand(time(NULL));
}

/**
 * Copies graph, not completed, matrix copying is not implemented
 * @param orig
 */
Graph::Graph(const Graph& orig) {
    minEdgeWeight = orig.minEdgeWeight;
    graphRegularity = orig.graphRegularity;
    maxCutWeight = orig.maxCutWeight;
    nodeCount = orig.nodeCount;
    //TODO copy matrix
}

/**
 * Deletes matrix
 */
Graph::~Graph() {
    unsigned int i;
    for(i=0; i < getNodeCount(); i++) {
        delete [] incidenceMatrix[i];
    }
    delete [] incidenceMatrix;
}

unsigned int Graph::getRegularity() const {
    return graphRegularity;
}

unsigned int Graph::getMinEdgeWeight() const {
    return minEdgeWeight;
}

unsigned int Graph::getMaxCutWeight() const {
    return maxCutWeight;
}

unsigned int Graph::getMaxCutWeightNode() const {
    return maxCutWeightNode;
}

unsigned int Graph::getNodeCount() const {
    return nodeCount;
}

/**
 *
 * @Deprecated
 * @return random number from <1, Graph::MAX_WEIGHT>
 */
unsigned int Graph::getRandomWeight() {
    return rand() % MAX_WEIGHT + 1;
}

/**
 * Shorthand for accessing matrix, bound checking implemented
 * @param i
 * @param j
 * @return Value on i, j position
 */
unsigned int Graph::getValue(unsigned int i, unsigned int j) {
    if (i >= nodeCount || j >= nodeCount) {
        return -1;
    }
    return incidenceMatrix[i][j];
}

/**
 * Input read. Matrix is allocated, all characteristics (regularity,
 * max cut weight, min edge weight) are computed and all values are loaded.
 * All edges are weighed with random number using Graph::getRandomWeight().
 * @param in
 * @param graph
 * @return
 */
istream & operator>>(istream &in, Graph &graph) {

    in >> graph.nodeCount;
    unsigned int nc = graph.getNodeCount();
    unsigned int totalSize = nc*nc;
    unsigned int i, k;
    unsigned int value;
    unsigned int nodeWeight = 0;

    graph.incidenceMatrix = new unsigned int * [nc];
    for (i=0; i < nc; i++) { // allocate rows
        graph.incidenceMatrix[i] = new unsigned int [nc];
    }

    graph.minEdgeWeight = graph.MAX_WEIGHT;
    graph.maxCutWeight = nc*graph.MAX_WEIGHT;
    
    for (i=0; i < totalSize; i++) { // coords: i/nc, i%nc
        in >> value;
        if (i/nc > i%nc) continue; // skip values under main diagonal (they are the same as those above)

        graph.incidenceMatrix[i/nc][i%nc] = value;
        graph.incidenceMatrix[i%nc][i/nc] = value;
        if(value > 0 && value < graph.minEdgeWeight) graph.minEdgeWeight = value; // min edge weight retrieval

        if (i%nc == nc-1) { // line has ended, count sum of edge weights for this node
            nodeWeight = 0;
            for (k = 0; k < nc; k++) {
                nodeWeight += graph.incidenceMatrix[i/nc][k];
            }
            if (nodeWeight < graph.getMaxCutWeight()) {
                graph.maxCutWeight = nodeWeight; // do we have a new max cut weight?
                graph.maxCutWeightNode = i/nc; // which node has the new max cut weight?
            }
        }

        // let's get regularity (aka in first row, count numbers other than zeros)
        if (i/nc == 0 && graph.incidenceMatrix[0][i] > 0) graph.graphRegularity++;
    }
    return in;
}

/**
 * Fancy output containing all information about this graph including incidence
 * matrix.
 * @param out
 * @param graph
 * @return
 */
ostream &operator<<(ostream &out, const Graph &graph) {

    out << "Graph input" << endl;
    out << setw(40) << setfill('=') << ' ' << endl;

    out << setfill(' ') << "Nr. of nodes: " << graph.getNodeCount() << endl;
    out << "Regularity: " << graph.getRegularity() << endl;
    out << "Min edge weight: " << graph.getMinEdgeWeight() << endl;
    out << "Max cut weight: " << graph.getMaxCutWeight() << endl;
    out << "Max cut weight node: " << graph.getMaxCutWeightNode() << endl;

    unsigned int i;
    unsigned int nc = graph.getNodeCount();
    for (i=0; i < nc; i++) {
        out << setw(5) << i << ": ";
        for(unsigned int j = 0; j <nc; j++) {
            out << setw(3) << graph.incidenceMatrix[i][j] << " ";
        }
        out << endl;
    }
    return out;
}

